package cn.hughie.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 二叉查找树
 *
 * @author yuh
 * @date 2018/5/17 17:29
 */
public class BST<K extends Comparable<K>, V> {


    /**
     * 节点
     */
    private class Node {
        Node left;
        Node right;
        int n;
        K key;
        V value;

        public Node(Node left, Node right, K key, V value) {
            this.left = left;
            this.right = right;
            this.key = key;
            this.value = value;
        }

        public Node() {
        }
    }

    /**
     * root为根节点
     */
    private Node root;

    /**
     * 总节点数
     *
     * @return
     */
    public int size() {
        return size(root);
    }

    /**
     * 以node为根的子树有几个节点
     *
     * @param node
     * @return
     */
    public int size(Node node) {
        if (node == null) {
            return 0;
        }
        return 1 + size(node.left) + size(node.right);
    }

    /**
     * 获取K
     *
     * @param key
     * @return
     */
    public K getKey(K key) {
        return getKey(root, key).key;
    }

    /**
     * 获取K
     *
     * @param node
     * @param key
     * @return
     */
    public Node getKey(Node node, K key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            return getKey(node.right, key);
        } else if (cmp < 0) {
            return getKey(node.left, key);
        } else {
            return node;
        }
    }

    /**
     * 插入元素
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        root = put(root, key, value);
    }

    /**
     * 插入节点到node的子树
     *
     * @param node
     * @param key
     * @param value
     */
    public Node put(Node node, K key, V value) {
        if (node == null) {
            return new Node(null, null, key, value);
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            node.right = put(node.right, key, value);
            node.n = size(node.left) + size(node.right) + 1;
        } else if (cmp < 0) {
            node.left = put(node.left, key, value);
            node.n = size(node.left) + size(node.right) + 1;
        } else {
            node.value = value;
        }

        return node;
    }

    /**
     * 全树最小元素
     *
     * @return
     */
    public K min() {
        return min(root).key;
    }


    /**
     * node子树最小元素
     *
     * @param node
     * @return
     */
    public Node min(Node node) {
        if (node == null) {
            return null;
        }

        if (node.left == null) {
            return node;
        }
        return min(node.left);

    }

    /**
     * 全树最大元素
     *
     * @return
     */
    public K max() {
        return max(root).key;
    }


    /**
     * node子树最大元素
     *
     * @param node
     * @return
     */
    public Node max(Node node) {
        if (node == null) {
            return null;
        }

        if (node.right == null) {
            return node;
        }
        return max(node.right);

    }

    /**
     * 返回小于等于这个节点的最接近节点
     *
     * @param key
     * @return
     */
    public K floor(K key) {
        return floor(root, key).key;
    }

    /**
     * 返回小于等于这个节点的最接近节点
     *
     * @param node
     * @param key
     * @return
     */
    public Node floor(Node node, K key) {
        if (node == null) {
            return null;
        }

        int cmp = key.compareTo(node.key);
        if (cmp == 0) {
            return node;
        }
        if (cmp < 0) {
            return floor(node.left, key);
        }

        Node right = floor(node.right, key);
        if (right != null) {
            return right;
        }
        return node;

    }

    /**
     * 返回大于等于这个节点的最接近节点
     *
     * @param key
     * @return
     */
    public K ceil(K key) {
        return ceil(root, key).key;
    }

    /**
     * 返回大于等于这个节点的最接近节点
     *
     * @param node
     * @param key
     * @return
     */
    public Node ceil(Node node, K key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp == 0) {
            return node;
        }
        if (cmp > 0) {
            return ceil(node.right, key);
        }

        Node left = ceil(node.left, key);
        if (left != null) {
            return left;
        }
        return node;
    }

    /**
     * 第n顺位 start with 0
     *
     * @param n
     * @return
     */
    public K select(int n) {
        return select(root, n).key;
    }


    /**
     * 第n顺位 start with 0
     *
     * @param node
     * @param n
     * @return
     */
    public Node select(Node node, int n) {
        if (node == null) {
            return null;
        }
        int t = size(node.left);
        if (n == t) {
            return node;
        } else if (n > t) {
            return select(node.right, n - t - 1);
        } else {
            return select(node.left, n);
        }
    }

    /**
     * 查看一个键的排位
     *
     * @param key
     * @return
     */
    public int rank(K key) {
        return rank(root, key);
    }

    /**
     * 查看一个键的排位
     *
     * @param node
     * @param key
     * @return
     */
    public int rank(Node node, K key) {
        if (node == null) {
            return Integer.MIN_VALUE;
        }
        int cmp = key.compareTo(node.key);
        if (cmp == 0) {
            return size(node.left);
        } else if (cmp > 0) {
            return size(node.left) + rank(node.right, key) + 1;
        } else {
            return rank(node.left, key);
        }
    }

    /**
     * 可迭代的K
     *
     * @return
     */
    public Iterable<K> keys() {
        return keys(min(), max());
    }


    /**
     * 创建队列
     *
     * @param min
     * @param max
     * @return
     */
    public Iterable<K> keys(K min, K max) {
        Deque<K> deque = new LinkedList<>();
        keys(root, deque, min, max);
        return deque;
    }

    /**
     * 中序遍历
     *
     * @param node
     * @param deque
     * @param min
     * @param max
     */
    public void keys(Node node, Deque<K> deque, K min, K max) {

        if (node == null) {
            return;
        }

        int cmplo = min.compareTo(node.key);
        int cmphi = max.compareTo(node.key);

        if (cmplo < 0) {
            keys(node.left, deque, min, max);
        }
        if (cmplo <= 0 && cmphi >= 0) {
            deque.addLast(node.key);
        }
        if (cmphi > 0) {
            keys(node.right, deque, min, max);
        }
    }

    /**
     * 删除最小值
     */
    public void delMin() {
        root = delMin(root);
    }

    /**
     * 删除最小值
     *
     * @param node
     * @return
     */
    public Node delMin(Node node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node.right;
        }
        node.left = delMin(node.left);
        node.n = size(node.left) + size(node.right) + 1;
        return node;

    }

    /**
     * 删除最大值
     */
    public void delMax() {
        root = delMax(root);
    }

    /**
     * 删除最大值
     *
     * @param node
     * @return
     */
    public Node delMax(Node node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node.left;
        }
        node.right = delMax(node.right);
        node.n = size(node.left) + size(node.right) + 1;
        return node;
    }

    /**
     * 删除指定节点
     */
    public void del(K key) {
        root = del(root, key);
    }

    /**
     * 删除指定节点
     *
     * @param node
     * @param key
     * @return
     */
    public Node del(Node node, K key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            node.left = del(node.left, key);
        } else if (cmp > 0) {
            node.right = del(node.right, key);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                //取右侧最小
                Node min = min(node.right);
                min.right = delMin(node.right);
                min.left = node.left;
                node = min;
            }
        }

        node.n = size(node.left) + size(node.right) + 1;
        return node;

    }


    public static void main(String[] args) {
        BST<Integer, Integer> bst = new BST<>();
        for (int i = 10; i > 0; i--) {
            if(i % 2 == 0){
                bst.put(10-i,i);
            }else{
                bst.put(i,i);
            }
        }
        Iterable<Integer> keys = bst.keys();
        System.out.println("iter:" + keys);
        System.out.println("min:" + bst.min());
        System.out.println("max:" + bst.max());
        System.out.println("rank 5:" + bst.rank(5));
        System.out.println("select 4:" + bst.select(4));
        System.out.println("delMin");
        bst.delMin();
        System.out.println("min:" + bst.min());
        System.out.println("delMax");
        bst.delMax();
        System.out.println("max:" + bst.max());

        System.out.println("iter:" + bst.keys());

        System.out.println("del 5");
        bst.del(5);
        System.out.println("iter:" + bst.keys());


        System.out.println("rank 5:" + bst.rank(5));
        System.out.println("select 4:" + bst.select(4));



    }

}
